public class Sort {

    // 直接插入排序的特性总结：
    //1. 元素集合越接近有序，直接插入排序算法的时间效率越高
    //2. 时间复杂度：O(N^2)
    //3. 空间复杂度：O(1)，它是一种稳定的排序算法
    //4. 稳定性：稳定
    public static void insertSort(int [] array){
        for(int i = 1;i<array.length;i++){
            int tmp = array[i];
            int j = i-1;
            for (; j>=0; j--) {
                if(array[j]>tmp){
                    array[j+1] =array[j];

                }else{
                    //x[j+1]=tmp;
                    break;
                }

            }
            array[j+1]=tmp;
        }

    }

    //1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
    //2. 时间复杂度：O(N^2)
    //3. 空间复杂度：O(1)
    //4. 稳定性：不稳定
    public static void pickSort(int []array){
        for (int i = 0; i < array.length; i++) {
            for (int j = i+1; j < array.length; j++) {
                if(array[j]<array[i]){
                    int tmp = array[i];
                    array[i] =array[j];
                    array[j] =tmp;
                }else {
                    break;
                }

            }

        }
    }

    //1. 堆排序使用堆来选数，效率就高了很多。
    //2. 时间复杂度：O(N*logN)
    //3. 空间复杂度：O(1)
    //4. 稳定性：不稳定
    public void createHeap(int [] array){
        for (int praent = (array.length-2)/2; praent >= 0 ; praent--) {
            shiftDown(praent,array.length,array);

        }
    }
  


    //向下调整
    private void shiftDown(int praent, int usedsize,int []array) {
        //左孩子的值
        int child =2*praent+1;
        while (child<usedsize) {
            if (child + 1<usedsize&&array[child] >  array[child + 1]) {
                child++;
            }
            if(array[child]<array[praent]){
                int tmp =array[praent];
                array[praent] = array[child];
                array[child] = tmp;
            }else {
                break;
            }
        }

    }
    public void swap(int [] array,int left,int right){
        int tmp = 0;

            tmp = array[left];
            array[left] = array[right];
            array[right] = tmp;


    }

    //挖坑法排序
   public static  void  kengSort1(int[] array,int left,int right){

       if (left >= right)
       return;
       int begin = left;
       int end =right;
       int key = array[begin];


         while (left<right){
            while (array[right]>key&&left<right){
                right--;
            }
             array[left] = array[right];

             while (array[left]<key&&left<right){
                 left++;
             }
             array[right] = array[left];

         }
        array[left] = key;
         int chile = left;

       kengSort1(array,begin,chile-1);
       kengSort1(array,chile+1,end);

    }






        /*
         * 计数排序
         *时间复杂度:O(N+范围)
         * 空间复杂度:O(范围)
         * 参数说明:
         *     a -- 待排序数组
         *     max -- 数组a中最大值的范围
         *
         */
        public static void countSort(int[] array) {
//            max 和 min 用于记录数组中的最大值和最小值。
//            range 计算出数组中元素的取值范围（即最大值与最小值之差加 1）。
//            count 数组用于记录每个元素出现的次数。
//            //1.假如最大值和最小值都是数据的第一个数
            int max = array[0];
            int min = array[0];
            //2.遍历找出数组的最大值和最小值
            for (int i = 1; i <array.length ; i++) {
                   if(array[i]>max){
                       max = array[i];
                   }
                   if(array[i]<min){
                       min=array[i];
                   }
            }
            //3.新建一个数组长度大小为array数组的（max-min+1）的
            int [] count = new int [max-min+1];
            //4.统计元素出现次数：
            //遍历输入数组，对于每个元素，计算其在 count 数组中的对应位置，并将该位置的值加 1。
            for (int i = 0; i < array.length; i++) {
                count[array[i]-min]++;
            }
            //5.
            int n = 0;
            for (int i = 0; i < count.length; i++) {
                while (count[i]>0){
                    array[n] = i+min;
                    n++;
                    count[i]--;

                }
            }


        }



}
